package cn.dapeng.tree.binary;

/**
 * 查找一个节点的后继节点
 * <p>
 * 什么是后继节点：
 * 二叉树中序遍历结果array，对于任何一个节点x，x的后继节点都是它当前下标+1
 * <p>
 * array[i]的后继节点array[i + 1]
 * <p>
 * <p>
 * 对于任何一个节点x
 * x如果有右孩子，它的后继节点都是它的右树的最左孩子
 * x如果没有右树，向上看，如果它是它父亲的右孩子，继续向上看，直到遍历到某个节点y，y是它父节点的左孩子，y的父节点就是x的后继节点
 * 只有两种情况，不看左子树，因为中序遍历先遍历左子树，所以左子树不可能是任何节点的后继节点
 */
public class SuccessorNode {

    /**
     * 这个二叉树有点特殊， 对于任何一个节点，  它都能找到它的父节点、左子树节点和右子树节点
     */
    public static class Node {
        public Node parent;
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }

    }

    public static Node getSuccessorNode(Node x) {
        if (x == null) {
            return null;
        }
        if (x.right != null) {
            return getLeftMost(x.right);
        } else {
            Node parent = x.parent;
            while (parent != null && parent.right == x) {
                x = parent;
                parent = x.parent;
            }
            return parent;
        }
    }

    /**
     * 有右树的情况下，查找后继节点
     *
     * @param x
     * @return
     */
    public static Node getLeftMost(Node x) {
        if (x == null) {
            return null;
        }

        while (x.left != null) {
            x = x.left;
        }
        return x;
    }

    public static void main(String[] args) {
        Node head = new Node(6);
        head.parent = null;
        head.left = new Node(3);
        head.left.parent = head;
        head.left.left = new Node(1);
        head.left.left.parent = head.left;
        head.left.left.right = new Node(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(9);
        head.right.parent = head;
        head.right.left = new Node(8);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(10);
        head.right.right.parent = head.right;

        Node test = head.left.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left.left.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left.right.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right.left.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right.right; // 10's next is null
        System.out.println(test.val + " next: " + getSuccessorNode(test));
    }


}
